Codeforces Round #658 Div2 A~D

本场链接:Codeforces Round #658
#A. Common Subsequence
A题太水了,不提.但是不知道为什么有人fst了这个题,等之后过来修一下.

#B. Sequential Nim
题目大意:有nn堆石子,每堆的数量是aia_i.两个人轮流玩这个游戏,每次可以从最左边的非空石堆里取出任意多个的石子.不能操作的人输,问是否先手必胜.
数据范围:
1n1051 \leq n \leq 10^5
1ai1091 \leq a_i \leq 10^9

这是一个很显然的博弈论模型,拿走最后一堆的人胜利,即整个游戏的结果与最后一堆无关.手玩几个样例之后可以发现序列里如果有11就会使情况变得不比较难缠,考虑简化一点的情况:除了最后一堆之前所有的石子都没有11个的.可以发现在这种情况下先手是一定必胜的,考虑加入11的影响:在看了样例之后可以很快的知道:11的数量是与结果无关的,答案应该和11是有关的,但不是数量问题.联想之前没有11的游戏过程:每次都是让先手的人拿石子出现一个11的局面,使第二个人只能选11个石子,可以想到关键点就是:谁拿到了11,或者可能是谁先拿到了非11的数.推理之后可以发现答案是后者,具体来说,游戏过程里谁先碰到了一个非11的数,谁就有主导权,一是把当前的数全部掏空,二是把当前的数变成一个11,不管怎样,主导权都在先拿到非11的人手上,最终一定是必胜的.
综上,结论:先拿到不是11的人胜利.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int win = 1;
		int n;scanf("%d",&n);
		vector<int> a(n + 17,0);
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		int i = 1;
		while(a[i] == 1)
		{
			if(i == n)	break;
			win ^= 1;
			++i;
		}
		if(!win)	puts("Second");
		else puts("First");
    }
    return 0;
}

#C. Prefix Flip
题目大意:给定两个二进制字符串aabb,里面只有0011两种元素.规定一种操作:选择aa里的一个前缀,先反转整个前缀里的所有状态(即0011,反之亦然),再反转整个前缀字符串.现要使aa变成bb,求操作次数和具体方案.

#C1
数据范围:
1n10001 \leq n \leq 1000
这个子问题中,操作次数不得大于3n3n

这题乍看上去很牛逼,正面突破看起来没什么性质,逆向考虑也是一样.不过这题规定了说操作不得多于3n3n次,也就是说对于每一位来说,操作都不得多于33次,即33是上界.如果能想办法找出一种,对每个位置来说,如果他需要修改,就最多只会用33次的方法,就可以通过本题了.
前面也说了,直接想要构造aabb的操作方案是很困难的,所以考虑对每一个不同的位置,从前往后考虑,我们要的就是,只改变当前这个位置的状态,而不修改前面的.比较容易想到如下的做法:每次先转一次当前这个位置的前缀,再转一次第一位(现在的第一位就是之前的最后一位),再转一次这个位置对应的前缀,就可以做到:不修改这个位置之前的内容,而把当前这个位置状态取反了.显然操作最多是3n3n次的,由此,可以轻松通过C1C1这个子问题.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int n;cin >> n;
		string a,b;cin >> a >> b;
		vector<int> res;
		for(int i = 0;i < n;++i)
		{
			if(a[i] != b[i])
			{
				res.push_back(i + 1);
				res.push_back(1);
				res.push_back(i + 1);
			}
		}
		cout << res.size() << " ";for(auto& v : res)	cout << v << " ";cout << endl;
	}
    return 0;
}

#C2
数据范围:
1n1051 \leq n \leq 10^5
操作次数不得超过2n2n

C2C2首先是把nn扩大到了10510^5级,且旋转次数降低成了2n2n.
把数量降低了之后,又看起来非常牛逼了,不过既然这个题拆成了两半,所以上一题的方式绝对不是毫无价值的,可以借鉴过来与这个题一起思考.很显然,我们这里是要找两步操作,这两步操作的操作次数上界是nn,两步合在一起就不超过2n2n了.上一问必须要3n3n的原因是对每一个字符都进行操作,每个不同的要消耗33个次数,产生了很多的冗余.C2C2解决的方向就是:整体考虑.
之前在C1C1里提到了说:想要直接把aa转成bb是十分困难的一件事,但是可以折中的考虑:有没有一种方式,能把aabb都变成一个相同的串,之后再把aa的操作部分和反转之后的bb的操作部分拼在一起,之后就是整个的操作方案了.第二步是比较好验证的,即反转之后的bb操作部分接过去肯定就是整个的操作方案,但是第一步比较困难,我们先梳理一下这个问题:找到一个特殊的串,使任意形态的aabb都能转移过来,并且一个串转到这种特殊串的代价的上界是小于等于nn的,这样,就可以解决C2C2了.
这个特殊的串,就是全部都是一个元素的串(这里构造00串,另外一种也肯定是一样的),具体怎么使一个串变成一个00串呢?只要把每一位和下一位不同的前缀转一次,就可以在上界不超过nn的情况下解决这个问题了,因为要的就是整个串都相同,把这一位转一下之后会使得这一位和下一位相同,并且依次进行的话,不会破坏前面已经排列好的串.不过特别注意一下,最后一个元素如果是11的话,说明构造出来的串是11串,还要额外的记录一次.最后,对aabb分别的做这个过程,并把bb的操作部分倒置一下,拼接起来就是最后的操作方案了,注意要先输出操作的步数.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int n;cin >> n;
		string a,b;cin >> a >> b;
		if(a == b)
		{
			cout << 0 << endl;
			continue;
		}
		vector<int> res;
		for(int i = 0;i < n - 1;++i)
			if(a[i] != a[i + 1])
				res.push_back(i + 1);
		if(a[n - 1] != '0')	res.push_back(n);
		vector<int> rev;
		for(int i = 0;i < n - 1;++i)
			if(b[i] != b[i + 1])
				rev.push_back(i + 1);
		if(b[n - 1] != '0')	rev.push_back(n);
		reverse(rev.begin(),rev.end());
		for(auto& v : rev)	res.push_back(v);
		cout << res.size() << " ";
		for(auto& v : res)	cout << v << " ";cout << endl;
	}
    return 0;
}

#D. Unmerge
题目大意:规定对两个数组aabb的合并(merge)操作:
①若其中一个是空,则合并结果是另外一个非空数组
②若a1<b1a_1<b_1,则先去掉aa数组的首位元素,之后的合并结果为a1+merge(a,b)a_1+merge(a,b).
③若a1>b1a_1>b_1,则先去掉bb数组的首位元素,之后的合并结果为b1+merge(a,b)b_1+merge(a,b).

给定一个长度为2n2*n的排列pp,问这个排列pp是否可以是某两个数组mergemerge后的结果,,并且要求这两个数组的长度均是nn,输出是或否即可,不需要输出具体方案是怎样的.

数据范围:
1n20001 \leq n \leq 2000
1pi2n1 \leq p_i \leq 2*n

这题乍看上去也很吊,nn20002000应该是一个O(n2)O(n^2)的算法,但是这个n2n^2也没得出太多的信息,可能就是一个dpdp,或者别的什么暴力遍历方法,没什么信息,还是去挖掘一下题目的性质.
从这个题目规定的操作来说,元素之间的关系,主要是大小关系,所以突破口应该是整个序列里的最值,这个最值可能跟mergemerge的构造顺序有关,很可能就是破开问题的关键.
顺着这个想法想,先找到整个排列pp里的最大值,假设他的位置是ii,那么对于ii之前的所有元素,肯定都是比他小的,如果要进行比较的话,肯定是前面的所有元素分配在前面就好,对于ii之后的元素,他们也肯定是比这个最大元素要小的,所以这些元素必须要在这个最大值后面,否则会导致位置不对.也就是说,在不考虑具体aabb之前,我们可以可以把整个序列按这种方式,从最大值一直往前依次分成若干个块,这每个块之间都是独立的,
例如对这个排列:613745826 1 3 7 4 5 8 2,分组之后就是(613),(745),(82)(6 1 3),(7 4 5),(8 2),在这些组之间,找一个空隙放入一个板子,左边的部分和右边的部分就各自是一个aabb的方案了,注意不能从中间插入板子,也不能破坏原来的顺序.
现在这个问题就很明确了,就是有若干组元素,每次你可以选一组元素加入到正在构造的序列里去,每个元素只有选和不选两种情况,长度就是价值,长度也是体积,这就是一个0101背包模型,直接做就可以了.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+7;
int f[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
    	memset(f,0,sizeof f);
    	int n;scanf("%d",&n);
    	int mx = 0;
    	vector<int> _w;
    	for(int i = 0;i < 2 * n;++i)	
    	{
    		int x;scanf("%d",&x);
    		if(x > mx)
    		{
    			_w.push_back(i);
    			mx = x;
    		}
    	}
    	_w.push_back(2 * n);
    	vector<int> w;
    	for(int i = 1;i < _w.size();++i)	w.push_back(_w[i] - _w[i - 1]);
    	for(int i = 0;i < w.size();++i)
    		for(int j = n;j >= w[i];--j)
    		{
    			assert(w[i] >= 0);
    			f[j] = max(f[j],f[j - w[i]] + w[i]);
    		}	
    	if(f[n] == n)	puts("YES");
    	else puts("NO");
    }
    return 0;
}

E看起来太牛逼了,以后有空补吧